package org.skywork.top.core.algorithm.list;

import org.skywork.top.core.algorithm.support.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 删除排序链表中的重复元素
 */
public class no_83 {

    /**
     * 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
     */

    static Map<Integer, Integer> map = new HashMap<>();
    public static ListNode deleteDuplicates(ListNode head) {

        /**
         * 示例 1：
         * 输入：head = [1,1,2]
         * 输出：[1,2]
         *
         * 示例 2：
         * 输入：head = [1,1,2,3,3]
         * 输出：[1,2,3]
         */

        if(head == null){
            return null;
        }

        if(head.next == null){
            if(map.get(head.val) != null){
                return null;
            }else{
                return head;
            }
        }

        ListNode newNode = null;
        if(map.get(head.val) != null && head.next != null){
            newNode = deleteDuplicates(head.next);
        }else{
            map.put(head.val, head.val);
            head.next = deleteDuplicates(head.next);
            newNode = head;
        }
        return newNode;
    }

    public ListNode deleteDuplicates2(ListNode head) {
        ListNode cur = head;
        while(cur != null && cur.next != null) {
            if(cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }


    public static void main(String[] args) {
        ListNode no1 = new ListNode(1, new ListNode(1, new ListNode(1)));
        ListNode listNode = deleteDuplicates(no1);
        System.out.println(listNode);
    }

}
